package com.zjj.lbw.algorithm.dp;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author zhanglei.zjj
 * @description 二维数组实现背包问题
 * @date 2023/4/5 10:29
 */
public class GameBag {
    public static void main(String[] args) {
        // 构造装备
        Element[] goods = {
                new Element("断玉匕", 1, 1500),
                new Element("天蚕甲", 4, 3000),
                new Element("金精玉魄剑", 3, 2000)};
        // 背包容量
        int bagSize = 4;
        ArrayElement[][] arrayElements = putBag(goods, bagSize);
        printArray(arrayElements);
    }

    /**
     * 将指定数量装备放入固定容量背包
     *
     * @param goods   游戏装备
     * @param bagSize 背包容量
     */
    public static ArrayElement[][] putBag(Element[] goods, int bagSize) {
        // 用二维数组来表示，我们动态规划思想分析过程中的表格
        ArrayElement[][] calcArray = new ArrayElement[goods.length][bagSize];

        for (int i = 0; i < goods.length; i++) {
            for (int j = 0; j < bagSize; j++) {
                // 第一行由于只有一件装备，因此无论背包有多大，最大价值也只能是这一件装备的价值
                if (i == 0) {
                    calcArray[i][j] = new ArrayElement(goods[i].value, goods[i]);
                    continue;
                }

                // 当前的最大价值
                int curMaxValue = 0;
                // 当前最大价值的装备组合
                Set<Element> curElementSet = new HashSet<>();

                // 是否选用当前装备
                boolean useCurGood = false;
                // 不选用当前装备最大价值
                int beforeRowMaxValue = calcArray[i - 1][j].value;

                // 如果当前背包能放得下，第 i 件装备
                if (j + 1 >= goods[i].cost) {
                    // 剩余格子价值
                    int remainValue = j + 1 - goods[i].cost > 0 ? calcArray[i - 1][j - goods[i].cost].value : 0;

                    // 选用当前装备最大价值
                    int useCurMaxValue = goods[i].value + remainValue;
                    if (useCurMaxValue > beforeRowMaxValue) {
                        useCurGood = true;
                        curMaxValue = useCurMaxValue;
                        if(remainValue > 0) {
                            curElementSet.addAll(calcArray[i - 1][j - goods[i].cost].elements);
                        }
                        curElementSet.add((goods[i]));
                    }
                }
                if (!useCurGood) {
                    curMaxValue = calcArray[i - 1][j].value;
                    curElementSet = calcArray[i - 1][j].elements;
                }
                calcArray[i][j] = new ArrayElement(curMaxValue, curElementSet);
            }
        }

        return calcArray;
    }

    /**
     * 打印二维数组
     * @param arrayElements
     */
    private static void printArray(ArrayElement[][] arrayElements) {
        for (int i = 0; i < arrayElements.length; i++) {
            System.out.println("当前行号：" + (i + 1));
            System.out.println(Arrays.toString(arrayElements[i]));
        }
    }

    /**
     * 数组元素对象建模
     */
    static class ArrayElement {
        /**
         * 计算后数组元素值
         */
        private int value;

        /**
         * 当前方案是由那些装备组成
         */
        private Set<Element> elements;

        public ArrayElement(int value, Element element) {
            this.value = value;
            HashSet<Element> elementSet = new HashSet<>();
            elementSet.add(element);
            this.elements = elementSet;
        }

        public ArrayElement(int value, Set<Element> elements) {
            this.value = value;
            this.elements = elements;
        }

        @Override
        public String toString() {
            return "ArrayElement{" +
                    "value=" + value +
                    ", elements=" + elements +
                    '}';
        }
    }

    /**
     * 装备对象建模
     */
    static class Element {
        /**
         * 装备名
         */
        private final String name;

        /**
         * 占用格子
         */
        private final Integer cost;

        /**
         * 物品的价值
         */
        private final Integer value;

        @Override
        public String toString() {
            return "Element{" +
                    "name='" + name + '\'' +
                    ", cost=" + cost +
                    ", value=" + value +
                    '}';
        }

        public Element(String name, Integer cost, Integer value) {
            this.name = name;
            this.cost = cost;
            this.value = value;
        }
    }
}
